package code401_500.code10_20;


import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，
 * 返回在甲板 board 上放置的 战舰 的数量。
 *
 * 战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，
 * 其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。
 *
 * 输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
 * 输出：2
 *
 * 输入：board = [["."]]
 * 输出：0
 */
public class _419countBattleships {

    // 思考 孤岛问题，图的遍历

    /**
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 76.71%     * 的用户
     * 内存消耗：     * 38.4 MB     * , 在所有 Java 提交中击败了     * 8.49%     * 的用户
     * @param board
     * @return
     */
    public static int countBattleships(char[][] board) {
        int[] dx = {1,0,0,-1};
        int[] dy = {0,1,-1,0};
        int ans = 0;
        int lenX = board.length;
        int lenY = board[0].length;

        // 不用新建立isUsed判断是否访问，改变原数组即可
        // 已访问的点位置设置为空格
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        for (int i = 0; i < lenX; i++) {
            for (int j = 0; j < lenY; j++) {
                if(board[i][j]==' '||board[i][j]=='.'){
                    continue;
                }else if(board[i][j]=='X'){
                    stack.addFirst(new int[]{i,j});
                    while (!stack.isEmpty()){
                        int[] node = stack.pollFirst();
                        for (int k = 0; k < 4; k++) {
                            int nowX = node[0]+dx[k];
                            int nowY = node[1]+dy[k];
                            if(nowX>=0&&nowY>=0&&nowX<lenX&&nowY<lenY&&board[nowX][nowY]=='X'){
                                stack.addFirst(new int[]{nowX,nowY});
                                board[nowX][nowY] = ' ';
                            }
                        }
                    }
                    ++ans;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        char[][] board = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
        System.out.println(countBattleships(board));
    }

    /**
     * 题解方法 ： 因为只有可能是水平或者垂直方向上的，故只需要判断一个点，检查左侧和上方是否是X。
     * 存在的话不是一艘新战舰。否则就增加一个新战舰
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.1 MB     * , 在所有 Java 提交中击败了     * 75.09%     * 的用户
     * @param board
     * @return
     */
    public int countBattleships1(char[][] board) {
        int m = board.length, n = board[0].length, ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    ans += (j > 0 && board[i][j-1] == 'X' ? 0 : (i > 0 && board[i-1][j] == 'X' ? 0 : 1));
                }
            }
        }
        return ans;
    }
}
